<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,100分)- 剩余银饰的重量（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>有 N 块二手市场收集的银饰&#xff0c;每块银饰的重量都是正整数&#xff0c;收集到的银饰会被熔化用于打造新的饰品。</p> 
<p>每一回合&#xff0c;从中选出三块最重的银饰&#xff0c;然后一起熔掉。</p> 
<p>假设银饰的重量分别为 x 、y和z&#xff0c;且 x ≤ y ≤ z。那么熔掉的可能结果如下&#xff1a;</p> 
<ul><li>如果 x &#61;&#61; y &#61;&#61; z&#xff0c;那么三块银饰都会被完全熔掉&#xff1b;</li><li>如果 x &#61;&#61; y 且 y !&#61; z&#xff0c;会剩余重量为 z - y 的银块无法被熔掉&#xff1b;</li><li>如果 x !&#61; y 且 y &#61;&#61; z&#xff0c;会剩余重量为 y - x 的银块无法被熔掉&#xff1b;</li><li>如果 x !&#61; y 且 y !&#61; z&#xff0c;会剩余重量为 z - y 与 y - x 差值 的银块无法被熔掉。</li></ul> 
<p>最后&#xff0c;</p> 
<ul><li>如果剩余两块&#xff0c;返回较大的重量&#xff08;若两块重量相同&#xff0c;返回任意一块皆可&#xff09;</li><li>如果只剩下一块&#xff0c;返回该块的重量</li><li>如果没有剩下&#xff0c;就返回 0</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入数据为两行&#xff1a;</p> 
<ul><li>第一行为银饰数组长度 n&#xff0c;1 ≤ n ≤ 40&#xff0c;</li><li>第二行为n块银饰的重量&#xff0c;重量的取值范围为[1&#xff0c;2000]&#xff0c;重量之间使用空格隔开</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>如果剩余两块&#xff0c;返回较大的重量&#xff08;若两块重量相同&#xff0c;返回任意一块皆可&#xff09;&#xff1b;</p> 
<p>如果只剩下一块&#xff0c;返回该块的重量&#xff1b;</p> 
<p>如果没有剩下&#xff0c;就返回 0。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3<br /> 1 1 1</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">0</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">选出1 1 1&#xff0c;得到 0&#xff0c;最终数组转换为 []&#xff0c;最后没有剩下银块&#xff0c;返回0</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3<br /> 3 7 10</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">选出 3 7 10&#xff0c;需要计算 (7-3) 和 (10-7) 的差值&#xff0c;即(7-3)-(10-7)&#61;1&#xff0c;所以数组转换为 [1]&#xff0c;剩余一块&#xff0c;返回该块重量&#xff0c;返回1</td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题应该只是一道逻辑模拟题。</p> 
<p></p> 
<p>我们需要每次取出所有银饰中的最重的三个x,y,z&#xff0c;然后按照题目要求的规则&#xff1a;</p> 
<ul><li>如果 x &#61;&#61; y &#61;&#61; z&#xff0c;那么三块银饰都会被完全熔掉&#xff1b;</li><li>如果 x &#61;&#61; y 且 y !&#61; z&#xff0c;会剩余重量为 z - y 的银块无法被熔掉&#xff1b;</li><li>如果 x !&#61; y 且 y &#61;&#61; z&#xff0c;会剩余重量为 y - x 的银块无法被熔掉&#xff1b;</li><li>如果 x !&#61; y 且 y !&#61; z&#xff0c;会剩余重量为 z - y 与 y - x 差值 的银块无法被熔掉。</li></ul> 
<p>这里的规则其实可以总结为一个公式&#xff1a;</p> 
<blockquote> 
 <p>Math.abs((z - y) - (y - x))</p> 
</blockquote> 
<p>带入上面x,y,z关系&#xff0c;即可推导出对应结果式。</p> 
<p></p> 
<p>这里需要注意的是&#xff0c;当 x !&#61; y 且 y !&#61; z&#xff0c;此时剩余重量为 z - y 与 y - x 差值 的银块&#xff0c;可能是0&#xff0c;即完全融掉的情况。</p> 
<p></p> 
<p>如果每次还有未熔完的银块&#xff0c;则重新加入到银饰中&#xff0c;然后再取出最重的三个银饰按照上面逻辑处理&#xff0c;直到所有银饰的数量不足三个&#xff0c;结束上面逻辑。</p> 
<p></p> 
<p>本题数量级不大&#xff0c;因此每次将未熔完的银块重新加入到银饰中后&#xff0c;可以对所有银饰进行重新排序。但是更优的做法是&#xff1a;</p> 
<p>我们只对初始所有银饰进行一次升序&#xff0c;之后取出尾部三个最重的银饰&#xff0c;如果有未熔完的银块remain&#xff0c;那么就在剩余银饰&#xff08;有序的&#xff09;进行二分查找remain的有序插入位置&#xff0c;进行插入&#xff0c;这样可以提高效率。</p> 
<p>关于二分查找有序插入位置可以看&#xff1a;</p> 
<p><a href="https://fcqian.blog.csdn.net/article/details/130097676" rel="nofollow" title="算法设计 - 二分法和三分法&#xff0c;洛谷P3382_二分法与三分法_伏城之外的博客-CSDN博客">算法设计 - 二分法和三分法&#xff0c;洛谷P3382_二分法与三分法_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  // 银饰数组长度
  const n &#61; parseInt(await readline());

  // n块银饰的重量
  const weights &#61; (await readline()).split(&#34; &#34;).map(Number);

  // 升序
  weights.sort((a, b) &#61;&gt; a - b);

  while (weights.length &gt;&#61; 3) {
    // 尾删三个最大值
    const z &#61; weights.pop();
    const y &#61; weights.pop();
    const x &#61; weights.pop();

    // 如果 x &#61;&#61; y &#61;&#61; z&#xff0c;那么下面公式结果&#xff1a;remain&#61;0, 表示三块银饰完全融掉
    // 如果 x &#61;&#61; y &amp;&amp; y !&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; z - y
    // 如果 x !&#61; y &amp;&amp; y &#61;&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; y - x
    // 如果 x !&#61; y &amp;&amp; y !&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; Math.abs((z - y) - (y - x))
    const remain &#61; Math.abs(z - y - (y - x));

    // 如果还有剩余银块
    if (remain !&#61; 0) {
      // 那么就二分查找其在剩余升序weights中的有序插入位置
      let idx &#61; binarySearch(weights, remain);

      if (idx &lt; 0) idx &#61; -idx - 1;

      // 在有序插入位置插入
      weights.splice(idx, 0, remain);
    }
  }

  if (weights.length &#61;&#61; 2) {
    // 如果剩余两块&#xff0c;返回较大的重量&#xff08;若两块重量相同&#xff0c;返回任意一块皆可&#xff09;
    console.log(Math.max(weights[0], weights[1]));
  } else if (weights.length &#61;&#61; 1) {
    // 如果只剩下一块&#xff0c;返回该块的重量
    console.log(weights[0]);
  } else {
    // 如果没有剩下&#xff0c;就返回 0
    console.log(0);
  }
})();

function binarySearch(nums, target) {
  let low &#61; 0;
  let high &#61; nums.length - 1;

  while (low &lt;&#61; high) {
    const mid &#61; (low &#43; high) &gt;&gt; 1;
    const midVal &#61; nums[mid];

    if (midVal &gt; target) {
      high &#61; mid - 1;
    } else if (midVal &lt; target) {
      low &#61; mid &#43; 1;
    } else {
      return mid;
    }
  }

  return -low - 1;
}
</code></pre> 
<p> </p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    // 银饰数组长度
    int n &#61; sc.nextInt();

    // n块银饰的重量
    LinkedList&lt;Integer&gt; weights &#61; new LinkedList&lt;&gt;();
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      weights.add(sc.nextInt());
    }

    // 升序
    weights.sort((a, b) -&gt; a - b);

    while (weights.size() &gt;&#61; 3) {
      // 尾删三个最大值
      int z &#61; weights.removeLast();
      int y &#61; weights.removeLast();
      int x &#61; weights.removeLast();

      // 如果 x &#61;&#61; y &#61;&#61; z&#xff0c;那么下面公式结果&#xff1a;remain&#61;0, 表示三块银饰完全融掉
      // 如果 x &#61;&#61; y &amp;&amp; y !&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; z - y
      // 如果 x !&#61; y &amp;&amp; y &#61;&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; y - x
      // 如果 x !&#61; y &amp;&amp; y !&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; Math.abs((z - y) - (y - x))
      int remain &#61; Math.abs((z - y) - (y - x));

      // 如果还有剩余银块
      if (remain !&#61; 0) {
        // 那么就二分查找其在剩余升序weights中的有序插入位置
        int idx &#61; Collections.binarySearch(weights, remain);

        if (idx &lt; 0) {
          idx &#61; -idx - 1;
        }

        // 在有序插入位置插入
        weights.add(idx, remain);
      }
    }

    if (weights.size() &#61;&#61; 2) {
      // 如果剩余两块&#xff0c;返回较大的重量&#xff08;若两块重量相同&#xff0c;返回任意一块皆可&#xff09;
      System.out.println(Math.max(weights.get(0), weights.get(1)));
    } else if (weights.size() &#61;&#61; 1) {
      // 如果只剩下一块&#xff0c;返回该块的重量
      System.out.println(weights.get(0));
    } else {
      // 如果没有剩下&#xff0c;就返回 0
      System.out.println(0);
    }
  }
}
</code></pre> 
<p> </p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
n &#61; int(input())
weights &#61; list(map(int, input().split()))


# 二分查找目标值位置&#xff0c;找不到则返回目标值在数组中有序插入位置
def binarySearch(nums, target):
    low &#61; 0
    high &#61; len(nums) - 1

    while low &lt;&#61; high:
        mid &#61; (low &#43; high) &gt;&gt; 1
        midVal &#61; nums[mid]

        if midVal &gt; target:
            high &#61; mid - 1
        elif midVal &lt; target:
            low &#61; mid &#43; 1
        else:
            return mid

    return -low - 1


# 算法入口
def getResult():
    weights.sort()

    while len(weights) &gt;&#61; 3:
        # 尾删三个最大值
        z &#61; weights.pop()
        y &#61; weights.pop()
        x &#61; weights.pop()

        # 如果 x &#61;&#61; y &#61;&#61; z&#xff0c;那么下面公式结果&#xff1a;remain&#61;0, 表示三块银饰完全融掉
        # 如果 x &#61;&#61; y &amp;&amp; y !&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; z - y
        # 如果 x !&#61; y &amp;&amp; y &#61;&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; y - x
        # 如果 x !&#61; y &amp;&amp; y !&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; Math.abs((z - y) - (y - x))
        remain &#61; abs((z - y) - (y - x))

        # 如果还有剩余银块
        if remain !&#61; 0:
            # 那么就二分查找其在剩余升序weights中的有序插入位置
            idx &#61; binarySearch(weights, remain)

            if idx &lt; 0:
                idx &#61; -idx - 1

            # 在有序插入位置插入
            weights.insert(idx, remain)

    if len(weights) &#61;&#61; 0:
        # 如果没有剩下&#xff0c;就返回 0
        return 0
    else:
        # 如果剩余两块&#xff0c;返回较大的重量&#xff08;若两块重量相同&#xff0c;返回任意一块皆可&#xff09;
        # 如果只剩下一块&#xff0c;返回该块的重量
        return max(weights)


# 算法调用
print(getResult())</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX(a, b) ((a) &gt; (b) ? (a) : (b))

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}

// 二分查找目标值位置&#xff0c;找不到则返回目标值在数组中有序插入位置
int binarySearch(const int *nums, int nums_size, int target) {
    int low &#61; 0;
    int high &#61; nums_size - 1;

    while (low &lt;&#61; high) {
        int mid &#61; (low &#43; high) &gt;&gt; 1;
        int midVal &#61; nums[mid];

        if (midVal &gt; target) {
            high &#61; mid - 1;
        } else if (midVal &lt; target) {
            low &#61; mid &#43; 1;
        } else {
            return mid;
        }
    }

    return -low - 1;
}

int main() {
    // 银饰数组长度
    int n;
    scanf(&#34;%d&#34;, &amp;n);

    // n块银饰的重量
    int weights[n];
    int weights_size &#61; 0;
    while (scanf(&#34;%d&#34;, &amp;weights[weights_size&#43;&#43;])) {
        if (getchar() !&#61; &#39; &#39;) break;
    }

    // 升序
    qsort(weights, n, sizeof(int), cmp);

    while (weights_size &gt;&#61; 3) {
        // 尾删三个最大值
        int z &#61; weights[weights_size - 1];
        int y &#61; weights[weights_size - 2];
        int x &#61; weights[weights_size - 3];

        weights_size -&#61; 3;

        // 如果 x &#61;&#61; y &#61;&#61; z&#xff0c;那么下面公式结果&#xff1a;remain&#61;0, 表示三块银饰完全融掉
        // 如果 x &#61;&#61; y &amp;&amp; y !&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; z - y
        // 如果 x !&#61; y &amp;&amp; y &#61;&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; y - x
        // 如果 x !&#61; y &amp;&amp; y !&#61; z&#xff0c;那么下面公式结果&#xff1a;remain &#61; Math.abs((z - y) - (y - x))
        int remain &#61; abs((z - y) - (y - x));

        // 如果还有剩余银块
        if (remain !&#61; 0) {
            // 那么就二分查找其在剩余升序weights中的有序插入位置
            int idx &#61; binarySearch(weights, weights_size, remain);

            if (idx &lt; 0) {
                idx &#61; -idx - 1;
            }

            // 在有序插入位置插入
            for (int i &#61; weights_size - 1; i &gt;&#61; idx; i--) {
                weights[i &#43; 1] &#61; weights[i];
            }
            weights[idx] &#61; remain;
            weights_size&#43;&#43;;
        }
    }

    if (weights_size &#61;&#61; 2) {
        // 如果剩余两块&#xff0c;返回较大的重量&#xff08;若两块重量相同&#xff0c;返回任意一块皆可&#xff09;
        printf(&#34;%d\n&#34;, MAX(weights[0], weights[1]));
    } else if (weights_size &#61;&#61; 1) {
        // 如果只剩下一块&#xff0c;返回该块的重量
        printf(&#34;%d\n&#34;, weights[0]);
    } else {
        // 如果没有剩下&#xff0c;就返回 0
        puts(&#34;0&#34;);
    }

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>